package me.timlong;

public class ArrayIntegerSearch {

    /**
     * 在一个二维数组中（每个一维数组的长度相同），
     * 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * @param target
     * @param array
     * @return
     */
    public boolean find(int target, int [][] array) {

//        a = [ 1 5 10 15 20
//              2 6 11 16 21
//              3 7 12 17 23
//              4 8 13 18 24 ]

        int rows = array.length;
        int cols = array[0].length;

        if(cols == 0 || rows == 0)
            return false;

        if(target < array[0][0] || target > array[rows - 1][cols - 1])
            return false;

        int i = 0, j = cols - 1;

        while(i < rows && j >= 0){
            if(target < array[i][j])
                j--;
            else if(target > array[i][j])  //千万注意时else if
                i++;
            else
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] array = {{1, 5, 10, 15, 20}, {2, 6, 11, 16, 21}, {3, 7, 12, 17, 23}, {4, 8, 13, 18, 24}};

//        for (int i = 0; i < 4; i++) {
//            for (int j = 0; j < 5; j++)
//                System.out.println(array[i][j] + "\t");
//            System.out.println();
//        }

        System.out.println(new ArrayIntegerSearch().find(23, array));
        System.out.println(new ArrayIntegerSearch().find(3, array));

    }


}
